package com.vincent.algorithms.sort;

import java.util.Arrays;

/**
 * 计数排序：核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。
 * 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数
 *
 * 它只能对整数进行排序(或者其他形式的转化为整数) 因为他是基于 数组下标表示大小  值表是个数
 *
 * 算法分析: 当输入的元素是n 个0到k之间的整数时，它的运行时间是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。
 * 由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，
 * 需要大量时间和内存。
 *
 * 时间复杂度 O(n+k) 平均 最好 最坏
 * 稳定性：稳定
 *
 * 计数排序需要占用大量空间，它仅适用于数据比较集中的情况。比如 [0~100]，[10000~19999] 这样的数据
 *
 * Created by yangwenchang on 2017/8/25.
 */
public class CountingSort {

    /**
     *
     * 这里默认 整数的范围是 0--k 需要的话可以自己遍历 算除最大最小值
     *
     * @param arr
     * @param k
     */
    public static void sort(int[] arr, int k) {

        int[] temp = new int[k + 1];
        for (int i = 0; i < arr.length; i++) {
            temp[arr[i]]++;
        }
//        倒数的方式 保证稳定性
        for (int j=k,o=arr.length-1;j>=0;j--){
            if(temp[j]>0) {
                arr[o--] = j;
            }
        }
        System.out.println(Arrays.toString(arr));
    }


    public static void main(String[] args) {
        int[] arr = {4,2,1,6,0,9,5};
        System.out.println(Arrays.toString(arr));
        sort(arr,10);
        System.out.println(Arrays.toString(arr));

    }


}

